package mdp;
public class longestCommonSubsequence {
    public int longestCommonSubsequence(String text1, String text2) {
        int count=0;
        int l1=text1.length(),l2=text2.length();
        //abcde  cdafff
        //acd  cda
        int[][] dp = new int[l1+1][l2+1];
        // for(int i=0;i<l1;i++){
        //     if(text1.charAt(i)==text2.charAt(0)){
        //         dp[i][0]=1;
        //     }
        // }
        // for(int i=0;i<l2;i++){
        //     if(text2.charAt(i)==text1.charAt(0)){
        //         dp[0][1]=1;
        //     }
        // }
        for(int i=1;i<=l1;i++){
            for(int j=1;j<=l2;j++){
                
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                    
                }else{
                    dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[l1][l2];
    }
    public static void main(String[] args) {
        longestCommonSubsequence obj = new longestCommonSubsequence();
        // String s1="bbm",s2="mb";
        // String s1="bsbininm",s2="jmjkbkjkv";
        // String s1="abcde",s2="cdafff";
        // String s1="abcde",s2="fg";
        String s1="abcde",s2="ace";
        System.out.println(obj.longestCommonSubsequence(s1, s2));
    }
}
